#include <iostream>
#include <random>
using namespace std;

// Insertion sort routine
template <typename Comparable>
void insertionSort(vector<Comparable> & a)
{
  for(int p = 1;p<a.size();++p)
    {
      Comparable tmp = move(a[p]);
      int j;
      for(j=p;j>0 && tmp <a[j-1]; --j)
	a[j]=move(a[j-1]);
      a[j]=move(tmp);
    }
}

// Code to perform median-of-three partitioning
template <typename Comparable>
const Comparable & median3(vector<Comparable> & a,int left,int right)
{
  int center = (left + right ) / 2;

  if(a[center] < a[left])
    swap(a[center] , a[left]);
  if(a[right] < a[left])
    swap(a[right] , a[left]);
  if(a[right] < a[center])
    swap(a[right] , a[center]);
  swap(a[center] , a[right-1] );
  return a[right - 1];
}

// Code to choose the pivot randomly
template <typename Comparable>
const Comparable & random(vector<Comparable> & a)
{
  int rp = rand()% a.size();
  return a[rp];
}

// Main quicksort routine
template <typename Comparable>
void quicksort_m(vector<Comparable> & a, int left, int right)
{
  if(left+10 <= right)
    {
      const Comparable & pivot = median3(a,left,right);
      int i = left,j = right -1;
      for(;;)
	{
	  while(a[++i]<pivot){}
	  while(pivot < a[--j]){}
	  if(i<j)
	    swap(a[i],a[j]);
	  else
	    break;
	}

      swap(a[i],a[right-1]);
      quicksort_m(a,left,i-1);
      quicksort_m(a,i+1,right);
    }
  else
    insertionSort(a);
}

// Driver for quicksort
template <typename Comparable>
void quicksort_median( vector<Comparable> & a)
      {
	quicksort_m(a,0, a.size() -1 );
      }


// Main quicksort routine
template <typename Comparable>
void quicksort_r(vector<Comparable> & a, int left, int right)
{
  if(left+10 <= right)
    {
      const Comparable & pivot = random(a);
      int i = left,j = right -1;
      for(;;)
	{
	  while(a[++i]<pivot){}
	  while(pivot < a[--j]){}
	  if(i<j)
	    swap(a[i],a[j]);
	  else
	    break;
	}

      swap(a[i],a[right-1]);
      quicksort_r(a,left,i-1);
      quicksort_r(a,i+1,right);
    }
  else
    insertionSort(a);
}


// Driver for quicksort
template <typename Comparable>
void quicksort_random( vector<Comparable> & a)
      {
	quicksort_r(a,0, a.size() -1 );
      }

// print elements
template <typename Comparable>
void print( vector<Comparable> & a)
    {
      for(int i=0;i<a.size();i++)
	cout<<a[i]<<" ";

      cout<<endl;
    }

